home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 401-425 / disk_419 / yacc / src.lzh / Src / lalr.c < prev    next >
C/C++ Source or Header  |  1990-07-14  |  10KB  |  639 lines
  1. #include "defs.h"
  2.  
  3. typedef
  4.   struct shorts
  5.     {
  6.       struct shorts *next;
  7.       short value;
  8.     }
  9.   shorts;
  10.  
  11. int tokensetsize;
  12. short *lookaheads;
  13. short *LAruleno;
  14. unsigned *LA;
  15. short *accessing_symbol;
  16. core **state_table;
  17. shifts **shift_table;
  18. reductions **reduction_table;
  19. short *goto_map;
  20. short *from_state;
  21. short *to_state;
  22.  
  23. short **transpose();
  24.  
  25. static int infinity;
  26. static int maxrhs;
  27. static int ngotos;
  28. static unsigned *F;
  29. static short **includes;
  30. static shorts **lookback;
  31. static short **R;
  32. static short *INDEX;
  33. static short *VERTICES;
  34. static int top;
  35.  
  36.  
  37. lalr()
  38. {
  39.     tokensetsize = WORDSIZE(ntokens);
  40.  
  41.     set_state_table();
  42.     set_accessing_symbol();
  43.     set_shift_table();
  44.     set_reduction_table();
  45.     set_maxrhs();
  46.     initialize_LA();
  47.     set_goto_map();
  48.     initialize_F();
  49.     build_relations();
  50.     compute_FOLLOWS();
  51.     compute_lookaheads();
  52. }
  53.  
  54.  
  55.  
  56. set_state_table()
  57. {
  58.     register core *sp;
  59.  
  60.     state_table = NEW2(nstates, core *);
  61.     for (sp = first_state; sp; sp = sp->next)
  62.     state_table[sp->number] = sp;
  63. }
  64.  
  65.  
  66.  
  67. set_accessing_symbol()
  68. {
  69.     register core *sp;
  70.  
  71.     accessing_symbol = NEW2(nstates, short);
  72.     for (sp = first_state; sp; sp = sp->next)
  73.     accessing_symbol[sp->number] = sp->accessing_symbol;
  74. }
  75.  
  76.  
  77.  
  78. set_shift_table()
  79. {
  80.     register shifts *sp;
  81.  
  82.     shift_table = NEW2(nstates, shifts *);
  83.     for (sp = first_shift; sp; sp = sp->next)
  84.     shift_table[sp->number] = sp;
  85. }
  86.  
  87.  
  88.  
  89. set_reduction_table()
  90. {
  91.     register reductions *rp;
  92.  
  93.     reduction_table = NEW2(nstates, reductions *);
  94.     for (rp = first_reduction; rp; rp = rp->next)
  95.     reduction_table[rp->number] = rp;
  96. }
  97.  
  98.  
  99.  
  100. set_maxrhs()
  101. {
  102.   register short *itemp;
  103.   register short *item_end;
  104.   register int length;
  105.   register int max;
  106.  
  107.   length = 0;
  108.   max = 0;
  109.   item_end = ritem + nitems;
  110.   for (itemp = ritem; itemp < item_end; itemp++)
  111.     {
  112.       if (*itemp >= 0)
  113.     {
  114.       length++;
  115.     }
  116.       else
  117.     {
  118.       if (length > max) max = length;
  119.       length = 0;
  120.     }
  121.     }
  122.  
  123.   maxrhs = max;
  124. }
  125.  
  126.  
  127.  
  128. initialize_LA()
  129. {
  130.   register int i, j, k;
  131.   register reductions *rp;
  132.  
  133.   lookaheads = NEW2(nstates + 1, short);
  134.  
  135.   k = 0;
  136.   for (i = 0; i < nstates; i++)
  137.     {
  138.       lookaheads[i] = k;
  139.       rp = reduction_table[i];
  140.       if (rp)
  141.     k += rp->nreds;
  142.     }
  143.   lookaheads[nstates] = k;
  144.  
  145.   LA = NEW2(k * tokensetsize, unsigned);
  146.   LAruleno = NEW2(k, short);
  147.   lookback = NEW2(k, shorts *);
  148.  
  149.   k = 0;
  150.   for (i = 0; i < nstates; i++)
  151.     {
  152.       rp = reduction_table[i];
  153.       if (rp)
  154.     {
  155.       for (j = 0; j < rp->nreds; j++)
  156.         {
  157.           LAruleno[k] = rp->rules[j];
  158.           k++;
  159.         }
  160.     }
  161.     }
  162. }
  163.  
  164.  
  165. set_goto_map()
  166. {
  167.   register shifts *sp;
  168.   register int i;
  169.   register int symbol;
  170.   register int k;
  171.   register short *temp_map;
  172.   register int state2;
  173.   register int state1;
  174.  
  175.   goto_map = NEW2(nvars + 1, short) - ntokens;
  176.   temp_map = NEW2(nvars + 1, short) - ntokens;
  177.  
  178.   ngotos = 0;
  179.   for (sp = first_shift; sp; sp = sp->next)
  180.     {
  181.       for (i = sp->nshifts - 1; i >= 0; i--)
  182.     {
  183.       symbol = accessing_symbol[sp->shift[i]];
  184.  
  185.       if (ISTOKEN(symbol)) break;
  186.  
  187.       if (ngotos == MAXSHORT)
  188.         fatal("too many gotos");
  189.  
  190.       ngotos++;
  191.       goto_map[symbol]++;
  192.         }
  193.     }
  194.  
  195.   k = 0;
  196.   for (i = ntokens; i < nsyms; i++)
  197.     {
  198.       temp_map[i] = k;
  199.       k += goto_map[i];
  200.     }
  201.  
  202.   for (i = ntokens; i < nsyms; i++)
  203.     goto_map[i] = temp_map[i];
  204.  
  205.   goto_map[nsyms] = ngotos;
  206.   temp_map[nsyms] = ngotos;
  207.  
  208.   from_state = NEW2(ngotos, short);
  209.   to_state = NEW2(ngotos, short);
  210.  
  211.   for (sp = first_shift; sp; sp = sp->next)
  212.     {
  213.       state1 = sp->number;
  214.       for (i = sp->nshifts - 1; i >= 0; i--)
  215.     {
  216.       state2 = sp->shift[i];
  217.       symbol = accessing_symbol[state2];
  218.  
  219.       if (ISTOKEN(symbol)) break;
  220.  
  221.       k = temp_map[symbol]++;
  222.       from_state[k] = state1;
  223.       to_state[k] = state2;
  224.     }
  225.     }
  226.  
  227.   FREE(temp_map + ntokens);
  228. }
  229.  
  230.  
  231.  
  232. /*  Map_goto maps a state/symbol pair into its numeric representation.    */
  233.  
  234. int
  235. map_goto(state, symbol)
  236. int state;
  237. int symbol;
  238. {
  239.     register int high;
  240.     register int low;
  241.     register int middle;
  242.     register int s;
  243.  
  244.     low = goto_map[symbol];
  245.     high = goto_map[symbol + 1];
  246.  
  247.     for (;;)
  248.     {
  249.     assert(low <= high);
  250.     middle = (low + high) >> 1;
  251.     s = from_state[middle];
  252.     if (s == state)
  253.         return (middle);
  254.     else if (s < state)
  255.         low = middle + 1;
  256.     else
  257.         high = middle - 1;
  258.     }
  259. }
  260.  
  261.  
  262.  
  263. initialize_F()
  264. {
  265.   register int i;
  266.   register int j;
  267.   register int k;
  268.   register shifts *sp;
  269.   register short *edge;
  270.   register unsigned *rowp;
  271.   register short *rp;
  272.   register short **reads;
  273.   register int nedges;
  274.   register int stateno;
  275.   register int symbol;
  276.   register int nwords;
  277.  
  278.   nwords = ngotos * tokensetsize;
  279.   F = NEW2(nwords, unsigned);
  280.  
  281.   reads = NEW2(ngotos, short *);
  282.   edge = NEW2(ngotos + 1, short);
  283.   nedges = 0;
  284.  
  285.   rowp = F;
  286.   for (i = 0; i < ngotos; i++)
  287.     {
  288.       stateno = to_state[i];
  289.       sp = shift_table[stateno];
  290.  
  291.       if (sp)
  292.     {
  293.       k = sp->nshifts;
  294.  
  295.       for (j = 0; j < k; j++)
  296.         {
  297.           symbol = accessing_symbol[sp->shift[j]];
  298.           if (ISVAR(symbol))
  299.         break;
  300.           SETBIT(rowp, symbol);
  301.         }
  302.  
  303.       for (; j < k; j++)
  304.         {
  305.           symbol = accessing_symbol[sp->shift[j]];
  306.           if (nullable[symbol])
  307.         edge[nedges++] = map_goto(stateno, symbol);
  308.         }
  309.     
  310.       if (nedges)
  311.         {
  312.           reads[i] = rp = NEW2(nedges + 1, short);
  313.  
  314.           for (j = 0; j < nedges; j++)
  315.         rp[j] = edge[j];
  316.  
  317.           rp[nedges] = -1;
  318.           nedges = 0;
  319.         }
  320.     }
  321.  
  322.       rowp += tokensetsize;
  323.     }
  324.  
  325.   SETBIT(F, 0);
  326.   digraph(reads);
  327.  
  328.   for (i = 0; i < ngotos; i++)
  329.     {
  330.       if (reads[i])
  331.     FREE(reads[i]);
  332.     }
  333.  
  334.   FREE(reads);
  335.   FREE(edge);
  336. }
  337.  
  338.  
  339.  
  340. build_relations()
  341. {
  342.   register int i;
  343.   register int j;
  344.   register int k;
  345.   register short *rulep;
  346.   register short *rp;
  347.   register shifts *sp;
  348.   register int length;
  349.   register int nedges;
  350.   register int done;
  351.   register int state1;
  352.   register int stateno;
  353.   register int symbol1;
  354.   register int symbol2;
  355.   register short *shortp;
  356.   register short *edge;
  357.   register short *states;
  358.   register short **new_includes;
  359.  
  360.   includes = NEW2(ngotos, short *);
  361.   edge = NEW2(ngotos + 1, short);
  362.   states = NEW2(maxrhs + 1, short);
  363.  
  364.   for (i = 0; i < ngotos; i++)
  365.     {
  366.       nedges = 0;
  367.       state1 = from_state[i];
  368.       symbol1 = accessing_symbol[to_state[i]];
  369.  
  370.       for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
  371.     {
  372.       length = 1;
  373.       states[0] = state1;
  374.       stateno = state1;
  375.  
  376.       for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
  377.         {
  378.           symbol2 = *rp;
  379.           sp = shift_table[stateno];
  380.           k = sp->nshifts;
  381.  
  382.           for (j = 0; j < k; j++)
  383.         {
  384.           stateno = sp->shift[j];
  385.           if (accessing_symbol[stateno] == symbol2) break;
  386.         }
  387.  
  388.           states[length++] = stateno;
  389.         }
  390.  
  391.       add_lookback_edge(stateno, *rulep, i);
  392.  
  393.       length--;
  394.       done = 0;
  395.       while (!done)
  396.         {
  397.           done = 1;
  398.           rp--;
  399.           if (ISVAR(*rp))
  400.         {
  401.           stateno = states[--length];
  402.           edge[nedges++] = map_goto(stateno, *rp);
  403.           if (nullable[*rp] && length > 0) done = 0;
  404.         }
  405.         }
  406.     }
  407.  
  408.       if (nedges)
  409.     {
  410.       includes[i] = shortp = NEW2(nedges + 1, short);
  411.       for (j = 0; j < nedges; j++)
  412.         shortp[j] = edge[j];
  413.       shortp[nedges] = -1;
  414.     }
  415.     }
  416.  
  417.   new_includes = transpose(includes, ngotos);
  418.  
  419.   for (i = 0; i < ngotos; i++)
  420.     if (includes[i])
  421.       FREE(includes[i]);
  422.  
  423.   FREE(includes);
  424.  
  425.   includes = new_includes;
  426.  
  427.   FREE(edge);
  428.   FREE(states);
  429. }
  430.  
  431.  
  432. add_lookback_edge(stateno, ruleno, gotono)
  433. int stateno, ruleno, gotono;
  434. {
  435.     register int i, k;
  436.     register int found;
  437.     register shorts *sp;
  438.  
  439.     i = lookaheads[stateno];
  440.     k = lookaheads[stateno + 1];
  441.     found = 0;
  442.     while (!found && i < k)
  443.     {
  444.     if (LAruleno[i] == ruleno)
  445.         found = 1;
  446.     else
  447.         ++i;
  448.     }
  449.     assert(found);
  450.  
  451.     sp = NEW(shorts);
  452.     sp->next = lookback[i];
  453.     sp->value = gotono;
  454.     lookback[i] = sp;
  455. }
  456.  
  457.  
  458.  
  459. short **
  460. transpose(R, n)
  461. short **R;
  462. int n;
  463. {
  464.   register short **new_R;
  465.   register short **temp_R;
  466.   register short *nedges;
  467.   register short *sp;
  468.   register int i;
  469.   register int k;
  470.  
  471.   nedges = NEW2(n, short);
  472.  
  473.   for (i = 0; i < n; i++)
  474.     {
  475.       sp = R[i];
  476.       if (sp)
  477.     {
  478.       while (*sp >= 0)
  479.         nedges[*sp++]++;
  480.     }
  481.     }
  482.  
  483.   new_R = NEW2(n, short *);
  484.   temp_R = NEW2(n, short *);
  485.  
  486.   for (i = 0; i < n; i++)
  487.     {
  488.       k = nedges[i];
  489.       if (k > 0)
  490.     {
  491.       sp = NEW2(k + 1, short);
  492.       new_R[i] = sp;
  493.       temp_R[i] = sp;
  494.       sp[k] = -1;
  495.     }
  496.     }
  497.  
  498.   FREE(nedges);
  499.  
  500.   for (i = 0; i < n; i++)
  501.     {
  502.       sp = R[i];
  503.       if (sp)
  504.     {
  505.       while (*sp >= 0)
  506.         *temp_R[*sp++]++ = i;
  507.     }
  508.     }
  509.  
  510.   FREE(temp_R);
  511.  
  512.   return (new_R);
  513. }
  514.  
  515.  
  516.  
  517. compute_FOLLOWS()
  518. {
  519.   digraph(includes);
  520. }
  521.  
  522.  
  523. compute_lookaheads()
  524. {
  525.   register int i, n;
  526.   register unsigned *fp1, *fp2, *fp3;
  527.   register shorts *sp, *next;
  528.   register unsigned *rowp;
  529.  
  530.   rowp = LA;
  531.   n = lookaheads[nstates];
  532.   for (i = 0; i < n; i++)
  533.     {
  534.       fp3 = rowp + tokensetsize;
  535.       for (sp = lookback[i]; sp; sp = sp->next)
  536.     {
  537.       fp1 = rowp;
  538.       fp2 = F + tokensetsize * sp->value;
  539.       while (fp1 < fp3)
  540.         *fp1++ |= *fp2++;
  541.     }
  542.       rowp = fp3;
  543.     }
  544.  
  545.   for (i = 0; i < n; i++)
  546.     for (sp = lookback[i]; sp; sp = next)
  547.       {
  548.         next = sp->next;
  549.         FREE(sp);
  550.       }
  551.  
  552.   FREE(lookback);
  553.   FREE(F);
  554. }
  555.  
  556.  
  557. digraph(relation)
  558. short **relation;
  559. {
  560.   register int i;
  561.  
  562.   infinity = ngotos + 2;
  563.   INDEX = NEW2(ngotos + 1, short);
  564.   VERTICES = NEW2(ngotos + 1, short);
  565.   top = 0;
  566.  
  567.   R = relation;
  568.  
  569.   for (i = 0; i < ngotos; i++)
  570.     INDEX[i] = 0;
  571.  
  572.   for (i = 0; i < ngotos; i++)
  573.     {
  574.       if (INDEX[i] == 0 && R[i])
  575.     traverse(i);
  576.     }
  577.  
  578.   FREE(INDEX);
  579.   FREE(VERTICES);
  580. }
  581.  
  582.  
  583.  
  584. traverse(i)
  585. register int i;
  586. {
  587.   register unsigned *fp1;
  588.   register unsigned *fp2;
  589.   register unsigned *fp3;
  590.   register int j;
  591.   register short *rp;
  592.  
  593.   int height;
  594.   unsigned *base;
  595.  
  596.   VERTICES[++top] = i;
  597.   INDEX[i] = height = top;
  598.  
  599.   base = F + i * tokensetsize;
  600.   fp3 = base + tokensetsize;
  601.  
  602.   rp = R[i];
  603.   if (rp)
  604.     {
  605.       while ((j = *rp++) >= 0)
  606.     {
  607.       if (INDEX[j] == 0)
  608.         traverse(j);
  609.  
  610.       if (INDEX[i] > INDEX[j])
  611.         INDEX[i] = INDEX[j];
  612.  
  613.       fp1 = base;
  614.       fp2 = F + j * tokensetsize;
  615.  
  616.       while (fp1 < fp3)
  617.         *fp1++ |= *fp2++;
  618.     }
  619.     }
  620.  
  621.   if (INDEX[i] == height)
  622.     {
  623.       for (;;)
  624.     {
  625.       j = VERTICES[top--];
  626.       INDEX[j] = infinity;
  627.  
  628.       if (i == j)
  629.         break;
  630.  
  631.       fp1 = base;
  632.       fp2 = F + j * tokensetsize;
  633.  
  634.       while (fp1 < fp3)
  635.         *fp2++ = *fp1++;
  636.     }
  637.     }
  638. }
  639.